// https://leetcode.cn/problems/squares-of-a-sorted-array/

// 算法思路总结：
// 1. 使用双指针从数组两端向中间遍历
// 2. 比较左右指针所指元素的平方值大小
// 3. 将较大的平方值从结果数组末尾向前放置
// 4. 时间复杂度：O(N)，空间复杂度：O(N)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<int> sortedSquares(vector<int>& nums) 
    {
        int m = nums.size();

        vector<int> ret(m);
        int left = 0, right = m - 1, index = m - 1;
        while (left <= right)
        {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];

            if (leftSquare <= rightSquare)
            {
                ret[index] = rightSquare;
                right--;
            }
            else 
            {
                ret[index] = leftSquare;
                left++;
            }
            index--;
        }

        return ret;
    }

    void printArray(vector<int>& nums)
    {
        for (const int& num : nums)
        {
            cout << num << " ";
        }
        cout << endl;
    }
};

int main()
{
    vector<int> nums1 = {-4,-1,0,3,10}, nums2 = {-7,-3,2,3,11};

    Solution sol;

    auto v1 = sol.sortedSquares(nums1), v2 = sol.sortedSquares(nums2);

    cout << "Array1:";
    sol.printArray(v1);

    cout << "Array2:";
    sol.printArray(v2);

    return 0;
}